// 给你一个整数数组 nums，请你将该数组升序排列。

// 你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

// 示例 1：
// 输入：nums = [5,2,3,1]
// 输出：[1,2,3,5]
// 解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。

// 示例 2：
// 输入：nums = [5,1,1,2,0,0]
// 输出：[0,0,1,1,2,5]
// 解释：请注意，nums 的值不一定唯一。

function sortArray(nums) {
  var len = nums.length;
  if (len < 2) {
    return nums;
  }
  // 选择中间位置作为基准值;
  var middle = Math.floor(len / 2),
    left = nums.slice(0, middle),
    right = nums.slice(middle);
  return merge(sortArray(left), sortArray(right)); // 采用自上而下的递归方法
}

function merge(left, right) {
  let res = [];
  let i = 0;
  let j = 0;
  let lenL = left.length;
  let lenR = right.length;
  // 合并两个有序数组
  // 比较两个数组的第一个元素，将较小的元素放到结果数组中
  while (i < lenL && j < lenR) {
    // 比较两个数组的第一个元素，将较小的元素放到结果数组中
    if (left[i] < right[j]) {
      res.push(left[i]);
      i++;
    } else {
      res.push(right[j]);
      j++;
    }
  }
  // 合并左数组剩余的元素
  while (i < lenL) res.push(left[i++]);
  // 合并右数组剩余的元素
  while (j < lenR) res.push(right[j++]);
  return res;
}
